package _01_第一季.树04.Tree03;

import java.util.Comparator;

public class AVLTree<E> extends BBST<E> {
    public AVLTree(){
        this(null);
    }

    public AVLTree(Comparator<E> comparator){
        super(comparator);
    }

    //内部节点类
    private static class AVLNode<E> extends Node<E>{
        int height = 1;
        public AVLNode(){
            this(null,null);
        }
        public AVLNode(E element,Node<E> parent){
            super(element, parent);
        }
        public int balanceFactory(){
            int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            return leftHeight - rightHeight;
        }
        //更新当前节点的高度
        public void updateHeight(){
            int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            height = 1 + Math.max(leftHeight,rightHeight);
        }
        public Node<E> tallerChild(){
            int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            if(leftHeight>rightHeight) return left;
            if(leftHeight<rightHeight) return right;
            return isLeftChild() ? left : right;
        }
        @Override
        public String toString() {
            String parentString = "null";
            if(parent!=null){
                parentString =parent.element.toString();
            }
            return element+"_"+parentString+"_"+height;
        }

    }

    /*
        需要找到高度最低的那一个不平衡的祖先节点
     */
    @Override
    protected void afterAdd(Node<E> node) {
       while((node=node.parent)!=null){
           if(isBalanced(node)){
               //如果平衡就更新高度
               updateHeight(node);
           }else{
               //可能导致多个祖父节点不平衡
               //但是只需要修复一次即可
               reBalanced(node);
               break;
           }
       }
    }

    //删除的哪一个节点
    //只会导致父节点或祖先节点失衡，只有一个节点失衡
    @Override
    protected void afterRemove(Node<E> node) {
        while((node=node.parent)!=null){
            if(isBalanced(node)){
                //如果平衡就更新高度
                updateHeight(node);
            }else{
                reBalanced(node);
            }
        }
    }

    @Override
    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        super.afterRotate(grand, parent, child);

        updateHeight(grand);
        updateHeight(parent);
    }

    /*
            平衡修复，传递过来的是高度最低的哪一个不平衡的父节点
            找到它的高度最高的两个子节点
         */
    private void reBalanced(Node<E> grand){
        Node<E> parent = ((AVLNode<E>)grand).tallerChild();
        Node<E> node =  ((AVLNode<E>)parent).tallerChild();
        if(parent.isLeftChild()){
            if(node.isLeftChild()){
                rotateRight(grand);
            }else{
                rotateLeft(parent);
                rotateRight(grand);
            }
        }else{
            if(node.isLeftChild()){
                rotateRight(parent);
                rotateLeft(grand);
            }else{
                rotateLeft(grand);
            }
        }

    }


    //更新节点高度
    private void updateHeight(Node<E> node){
        ((AVLNode<E>)node).updateHeight();
    }

    //判断该节点是否平衡
    private boolean isBalanced(Node<E> node){
        return Math.abs(((AVLNode<E>)node).balanceFactory()) <= 1;
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element,parent);
    }
}
